package top150;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class TOP150 {
    public static void main(String[] args) {

    }
}

/**
 * 双指针top150
 */
class Top150TwoPointers{
    /**125. 验证回文串  使用内置函数
     * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
        字母和数字都属于字母数字字符。
        给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
     */
    public static boolean isPalindrome1(String s) {
        if(s.length() == 0 || s.length() == 1) return true;
        StringBuilder sb = new StringBuilder(s.toLowerCase());
        for(int i = sb.length() - 1; i >= 0; i--){
            char ch = sb.charAt(i);
            if(ch < '0' || (ch > '9' && ch < 'a') || ch > 'z'){
                sb.deleteCharAt(i);
            }
        }
        return sb.toString().equals(sb.reverse().toString());
    }

    /** 125. 验证回文串 双指针一次遍历
     * 
     * @param s
     * @return
     */
    public static boolean isPalindrome2(String s){
        if(s.length() <= 1) return true;
        StringBuilder sb = new StringBuilder(s);
        int i = 0, j = sb.length() - 1;
        while(i <= j){
            while(!isLetterand(sb.charAt(i))) i++;
            while(!isLetterand(sb.charAt(j))) j--;
            if(sb.charAt(i)>'A'&&sb.charAt(i)<'Z'){
                char ch = sb.charAt(i);
                ch += 32;
                sb.setCharAt(i, ch);
            }
            if(sb.charAt(j)>'A'&&sb.charAt(j)<'Z'){
                char ch = sb.charAt(j);
                ch += 32;
                sb.setCharAt(j, ch);
            }
            if(i <= j && sb.charAt(i) != sb.charAt(j)){
                return false;
            }
            i++;j--;
        }
        return true;
    }
    private static boolean isLetterand(char ch){
        if((ch>'0'&&ch<'9')||(ch>'a'&&ch<'z') || (ch>'A'&&ch<'Z'))
            return true;
        return false;
    }

    /** 125. 验证回文串 双指针优化版本
     * 
     */
    public static boolean isPalindrome(String s){
        if(s.length() <= 1) return true;
        int i = 0, j = s.length() - 1;
        while(i <= j){
            if(!Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }else if(!Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }else if(Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))){
                i++;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }


    /**392. 判断子序列
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     */

    public static boolean isSubsequence1(String s, String t) {
        if(s.length() == 0) return true;
        int i = 0, j = 0;
        while(i < s.length() && j < t.length()){
            if(s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            }else{
                j++;
            }
        }

        // 结束时子串来到最后
        if(i >= s.length())
            return true;
        return false;
    }

    /**392. 判断子序列 优化版本
     * 
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence(String s, String t) {
        if(s.length() == 0) return true;
        int i = 0, j = 0;
        while(i < s.length() && j < t.length()){
            if(s.charAt(i) == t.charAt(j++) && ++i == s.length())
                return true;
        }
        return false;
    }

    /**01. 两数之和  暴力枚举
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
        你可以按任意顺序返回答案。
     */
    public static int[] twoSum1(int[] nums, int target) {
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }
        return null;
    }

    /**01. 两数之和  哈希表，空间换时间 
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        // 差值结果，下标
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        for(int i = 0; i < nums.length; i++){
            int res = target - nums[i];
            if(map.getOrDefault(res, null) != null && map.get(res) != i){
                return new int[]{i, map.get(res)};
            }
        }
        return null;
    }

    /**167. 两数之和 II - 输入有序数组
     * 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

        以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

        你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

        你所设计的解决方案必须只使用常量级的额外空间。
     */
    public static int[] twoSum(int[] nums, int target){
        int i = 0, j = nums.length - 1;
        while(i < j){
            int sum = nums[i] + nums[j];
            if(sum == target && i != j){
                return new int[]{i + 1, j + 1};
            }
            if(sum > target)
                j--;
            else
                i++;
        }
        return null;
    }

    /**
     * 15. 三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
     */
    
}

/**
 * 滑动窗口top150
 */
class Top150SlidingWindow {
    /**
     * 209. 长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 
     * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * 子数组 是数组中连续的 非空 元素序列。
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int s = nums[0], ans = Integer.MAX_VALUE;
        int right = 0, left = 0, len = nums.length;
        while(right < len && left <= right){
            if(s < target && ++right < len){
                s += nums[right];
            }else if(s >= target){
                ans = Math.min(ans, right - left + 1);
                s -= nums[left++];
            }
        }
        return ans;
    }

    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
     * 子字符串 是字符串中连续的 非空 字符序列。
     */
    public static int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len == 0) return 0;
        Map<Character, Integer> m = new HashMap<>();
        m.merge(s.charAt(0), 1, Integer::sum);
        int left = 0, right = 0, ans = Integer.MIN_VALUE;
        while(left <= right && right < len){
            if(m.size() == right - left + 1){
                ans = Math.max(ans, m.size());
                if(++right < len){
                    m.merge(s.charAt(right), 1, Integer::sum);
                }
            } else {
                int c = m.get(s.charAt(left));
                if(c > 1) m.merge(s.charAt(left++), -1, Integer::sum);
                else m.remove(s.charAt(left++));
            }
        }
        return ans;
    }

    /**
     * 30. 串联所有单词的子串
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        // 这里的哈希表需要反过来思考
        // 定长滑动窗口：先统计词频，表示当前窗口内缺少的词的数量
        // 若为负数，表示当前窗口内多余的词的数量
        // 当词的数量不多也不少即==0时，删除该词频记录，当词频表无数据时，表示成功匹配
        Map<String, Integer> mapCount = new HashMap<>();
        // 记录可以被词频统计的词
        Set<String> wordsSet = new HashSet<>();
        /**
         * 右窗口边界逻辑：
         * 1. 进入可以被统计的词时，词频-1，如果 词频==0，则移除
         * 左窗口逻辑：
         * 1. 出去可以被溶剂的词时，词频+1，如果 词频==0，则移除
         */
        for(String word : words){
            mapCount.merge(word, 1, Integer::sum);
            wordsSet.add(word);
        }
        List<Integer> ans = new ArrayList<>();
        int winSize = words[0].length() * words.length, step = words[0].length();
        for(int offset = 0; offset < step; offset++){
            // 每次偏移 单独维护一个词频副本
            Map<String, Integer> wordsMap = new HashMap<>(mapCount);
            for(int i = offset + step - 1; i < s.length(); i += step){
                // 进入窗口
                String str = s.substring(i - step + 1, i + 1);
                if(wordsSet.contains(str)){
                    wordsMap.merge(str, -1, Integer::sum);
                    if(wordsMap.get(str) == 0)
                        wordsMap.remove(str);
                }

                // 左窗口处理
                int left = i - winSize + 1;
                if(left < 0) continue;

                // 统计答案
                if(wordsMap.size() == 0)
                    ans.add(left);

                // 左边出去
                str = s.substring(left, left + step);
                if(wordsSet.contains(str)){
                    wordsMap.merge(str, 1, Integer::sum);
                    if(wordsMap.get(str) == 0)
                        wordsMap.remove(str);
                }
            }
        }
        return ans;
    }


}

/**
 * 链表 top150
 */
class Top150LinkedList{
    class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int val){ this.val = val; }
        ListNode(int val, ListNode next){
            this.val = val;
            this.next = next;
        }
    }
    /**
     * 2. 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

        请你将两个数相加，并以相同形式返回一个表示和的链表。

        你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        ListNode p1 = l1, p2 = l2;
        int sum = 0;
        while(p1 != null || p2 != null || sum != 0){
            if(p1 != null){
                sum += p1.val;
                p1 = p1.next;
            }
            if(p2 != null){
                sum += p2.val;
                p2 = p2.next;}
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = node;
            sum /= 10;
        }
        return dummy.next;
        
    }

    /**
     * 21. 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0), p = dummy;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        while(list1 != null){
            p.next = list1;
            list1 = list1.next;
            p = p.next;
        }
        while(list2 != null){
            p.next = list2;
            list2 = list2.next;
            p = p.next;
        }
        return dummy.next;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 138. 随机链表的复制
     * @param head
     * @return
     */
    public Node copyRandomList1(Node head) {
        if(head == null) return null;
        // 在每个节点的后面挂上一个新的节点
        Node dummy = new Node(0);
        dummy.next = head;
        Node p = dummy.next;
        while(p != null){
            Node node = new Node(p.val);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        // 复制被挂节点的随机指针
        p = dummy.next;
        while(p != null){
            Node p2 = p.next;
            if(p.random != null)
                p2.random = p.random.next;
            p = p2.next;
        }
        // 将新节点抽离出来
        p = dummy.next;
        Node cur = dummy;
        while(p != null){
            cur.next = p.next;
            cur = p.next;
            p.next = cur.next;
            p = p.next;
        }
        cur.next = null;
        return dummy.next;
    }

    public Node copyRandomList(Node head) {
        // 递归回溯
        // key:旧节点  val:新节点
        Map<Node, Node> m = new HashMap<>();
        return copyRandomListCore(head, m);
    }

    private Node copyRandomListCore(Node node, Map<Node, Node> m){
        if(node == null) return null;

        Node newNode = new Node(node.val);
        m.put(node, newNode);
        newNode.next = copyRandomListCore(node.next, m);
        if(node.random != null)
            newNode.random = m.get(node.random);
        return newNode;
    }

    /**
     * 92. 反转链表 II
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 迭代反转
        if(head == null || left == right) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy; // 前一个位置
        for(int i = 1; i < left; i++){
            prev = prev.next;
        }
        // start在left位置，then在left下一个位置
        ListNode start = prev.next, then = start.next;
        for(int i = 0; i < right - left; i++){
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }



    /**
     * 61. 旋转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0) return head;
        int length = 1;
        ListNode last = head;
        while(last.next != null){
            last = last.next;
            length++;
        }
        k = length - k % length;
        if(k == length) return head;
        ListNode prev = head;
        for(int i = 1; i < length; i++){
            if(i == k)
                break;
            else
                prev = prev.next;

        }

        ListNode newHead = prev.next;
        prev.next = last.next;
        last.next = head;
        return newHead;
    }

}

/**
 * 栈 top150
 */
class Top150Stack{
    /**
     * 20. 有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

        有效字符串需满足：

        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
        每个右括号都有一个对应的相同类型的左括号。
     */
    static boolean isValid(String str) {
        if(str.length() % 2 == 1) return false;
        Map<Character, Character> m = Map.of(
            '}','{',
            ')','(',
            ']','['
        );
        Stack<Character> s = new Stack<>();
        int index = 0;
        while(index < str.length()){
            if(null != m.getOrDefault(str.charAt(index), null)){
                if(
                    !s.empty() && 
                    s.peek().equals(m.get(str.charAt(index)))
                ){
                    s.pop();
                } else{
                    return false;
                }
            } else {
                s.push(str.charAt(index));
            }
            index++;
        }
        return s.empty();
    }

    /**
     * 71. 简化路径
     */
    static String simplifyPath(String path) {
        List<String> ans = new ArrayList<>();
        // 使用split时，如果出现连续的/////,将划分出出空字符串""这个样子就很不好了就哈哈哈，是吧哈哈哈，是的
        for(String s : path.split("/")){
            if(s.isEmpty() || s.equals("."))
                continue;
            if(s.equals("..")){
                if(ans.size() > 0)
                    ans.removeLast();
            } else {
                ans.add(s);
            }
        }
        return "/" + String.join("/", ans);
    }

    /**
     * 155. 最小栈
     */
    class MinStack {

        private final List<Integer> stack;
        private final List<Integer> minStack;

        /**
         * 构造函数
         * 初始化最小栈
         */
        public MinStack() {
            stack = new ArrayList<>();
            minStack = new ArrayList<>();
        }
        
        /**
         * 将元素压入栈
         * @param val 要压入栈的值
         */
        public void push(int val) {
            stack.add(val);
            if(minStack.size() == 0){
                minStack.add(val);
            } else {
                minStack.add(Math.min(minStack.getLast(), val));
            }
        }
        
        /**
         * 弹出栈顶元素，不用考虑空调用
         */
        public void pop() {
            stack.removeLast();
            minStack.removeLast();
        }
        
        /**
         * 获取栈顶元素, 不考虑空调用
         * @return 栈顶元素的值
         */
        public int top() {
            return stack.getLast();
        }
        
        /**
         * 获取栈中的最小元素， 不考虑空调用
         * @return 栈中的最小值
         */
        public int getMin() {
            return minStack.getLast();
        }
    }

    /**
     * 150. 逆波兰表达式求值
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

        请你计算该表达式。返回一个表示表达式值的整数。

        注意：

        有效的算符为 '+'、'-'、'*' 和 '/' 。
        每个操作数（运算对象）都可以是一个整数或者另一个表达式。
        两个整数之间的除法总是 向零截断 。
        表达式中不含除零运算。
        输入是一个根据逆波兰表示法表示的算术表达式。
        答案及所有中间计算结果可以用 32 位 整数表示。

        示例 1：
        输入：tokens = ["2","1","+","3","*"]
        输出：9
        解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

        示例 2：
        输入：tokens = ["4","13","5","/","+"]
        输出：6
        解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

        示例 3：
        输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
        输出：22
        解释：该算式转化为常见的中缀算术表达式为：
        ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
        = ((10 * (6 / (12 * -11))) + 17) + 5
        = ((10 * (6 / -132)) + 17) + 5
        = ((10 * 0) + 17) + 5
        = (0 + 17) + 5
        = 17 + 5
        = 22
     */
    public static int evalRPN(String[] tokens) {
        Set<String> options = Set.of("+","-", "*", "/");
        Stack<String> s = new Stack<>();
        for(int i = 0; i < tokens.length; i++){
            if(options.contains(tokens[i])){
                int b = Integer.parseInt(s.pop());
                int a = Integer.parseInt(s.pop());
                int c;
                if(tokens[i].equals("+")){
                    c = a + b;
                } else if(tokens[i].equals("-")){
                    c = a - b;
                } else if(tokens[i].equals("*")){
                    c = a * b;
                } else {
                    c = a / b;
                }
                s.push(String.valueOf(c));
            } else {
                s.push(tokens[i]);
            }
        }
        return Integer.parseInt(s.pop());
    }


    /**
     * 224. 基本计算器
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

    注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。


    初始化一个空栈（用于存放操作符）
    初始化一个空输出队列（用于存放后缀表达式）
    从左到右扫描中缀表达式的每个元素：
            如果是数字：直接加入输出队列
            如果是 (：压入栈
            如果是 )：将栈中元素弹出并加入输出队列，直到遇到 (，然后弹出 (（不加入输出）
            如果是 + 或 -：
                当栈顶是 + 或 - 时，它们优先级相等，先弹出栈顶操作符加入输出（左结合性）
                然后将当前操作符压入栈
            扫描结束后，将栈中剩余操作符全部弹出到输出队列
     */
    
    public static int calculate(String str) {
        str = str.replace(" ", "");
        // 转化为逆波兰表达式
        Queue<String> nums = new java.util.LinkedList<>(); // 数字队列
        Stack<Character> opts = new Stack<>(); // 操作符栈
        for(int i = 0; i < str.length(); i++){
            char ch = str.charAt(i);
            // 判断是否是一元运算符的负号
            // 负号在开头，或者负号前边是 (
            if(ch == '-'){
                if(i == 0 || str.charAt(i - 1) == '('){
                    nums.add("0");
                }
            }

            // 如果是数字
            if(Character.isDigit(ch)){
                String num = new String();
                while(i < str.length()){
                    if(Character.isDigit(str.charAt(i))){
                        num += str.charAt(i);
                        i++;
                    } else {
                        i--;
                        break;
                    }
                }
                nums.add(num);
            } else if(ch == ')') {
                // 弹出操作符栈直至遇到 (
                while(!opts.empty()){
                    if(opts.peek() != '('){
                        nums.add(String.valueOf(opts.pop()));
                    } else {
                        opts.pop();
                        break;
                    }
                }
            } else if(ch == '('){
                opts.push(ch);
            } else {
                if(!opts.empty() && (opts.peek() == '+' || opts.peek() == '-')){
                    nums.add(String.valueOf(opts.pop()));
                }
                opts.push(ch);
            }
        }
        while(!opts.empty()){
            nums.add(String.valueOf(opts.pop()));
        }
        StringBuilder sb = new StringBuilder();
        while (nums.size() > 1) {
            sb.append(nums.remove() + ",");
        }
        if(nums.size() == 1){
            sb.append(nums.remove());
        }
        String[] tokens = sb.toString().split(",");
        return evalRPN(tokens);
    }

     

}

/**
 * 图
 */
class Top150Graph{
    /**
     * 200. 岛屿数量
     * DFS
     */
    public int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m * n; i++){
            if(grid[i / n][i % n] == '1'){
                count++;
                numIslandsCore(grid, i / n, i % n);
            }
        }
        return count;
    }
    /**
     * 把所有DFS走过的陆地全改成 0
     * @param grid
     */
    private void numIslandsCore(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        numIslandsCore(grid, i + 1, j);
        numIslandsCore(grid, i - 1, j);
        numIslandsCore(grid, i, j + 1);
        numIslandsCore(grid, i, j - 1);
    }



    /**
     * 130. 被围绕的区域
     */
    public void solve(char[][] board) {
        Set<Integer> fill = new HashSet<>();
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m * n; i++){
            if(board[i / n][i % n] == 'O'){
                if(solveCore(board, fill, i / n, i % n)){
                    // 当前DFS过程中没有碰到边界
                    for(int index : fill){
                        board[index / n][index % n] = 'X';
                    }
                }
                fill.clear();
            }
        }
    }
    public boolean solveCore(char[][] board, Set<Integer> fill, int i, int j){
        // 一定存在边上的 O
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        // 在边界上
        if(i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1){
            if(board[i][j] == 'O')
                return false;
            return true;
        }
        // 在内部
        if(board[i][j] == 'X' || fill.contains(board[0].length * i + j)) return true;
        fill.add(board[0].length * i + j);
        boolean isfill =solveCore(board, fill, i + 1, j) &&
            solveCore(board, fill, i - 1, j) &&
            solveCore(board, fill, i, j + 1) &&
            solveCore(board, fill, i, j - 1);
        return isfill;
    }

    /**
     * 130. 被围绕的区域，内存优化
     * 从边界上的 'O' 开始 DFS/BFS，把所有与边界连通的 'O' 标记为特殊字符（如 'A'），最后再遍历整个图，把剩下的 'O' 变成 'X'，把 'A' 恢复为 'O'
     */
    public void solveOpt(char[][] board) {
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O') solveOptCore(board, i, 0, 'O', 'A');
            if(board[i][n - 1] == 'O') solveOptCore(board, i, n - 1, 'O', 'A');
        }
        for(int j = 0; j < n; j++){
            if(board[0][j] == 'O') solveOptCore(board, 0, j, 'O', 'A');
            if(board[m - 1][j] == 'O') solveOptCore(board, m - 1, j, 'O', 'A');
        }

        for(int i = 0; i < m * n; i++){
            if(board[i / n][i % n] == 'O'){
                solveOptCore(board, i / n, i % n, 'O', 'X');
            }
            if(board[i / n][i % n] == 'A'){
                solveOptCore(board, i / n, i % n, 'A', 'O');
            }
        }
    }
    public void solveOptCore(char[][] board, int i, int j, char ch1, char ch2){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        if(board[i][j] != ch1) return;
        board[i][j] = ch2;
        solveOptCore(board, i + 1, j, ch1, ch2);
        solveOptCore(board, i - 1, j, ch1, ch2);
        solveOptCore(board, i, j + 1, ch1, ch2);
        solveOptCore(board, i, j - 1, ch1, ch2);
    }





}



































